package algorithm.fibonacci;

import java.util.Arrays;

/**
 * 斐波拉契数列
 *
 * @author 杨 强
 * @package algorithm.fibonacci
 * @createTime 2023-03-06 22:41
 */
public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(f2(10));
    }

    /**
     * 第二版:用记忆法优化
     * @param n
     * @return
     */
    public static int f2(int n){
        // 初始化一个数组用于存储已经计算的值
        int[] cache = new int[n + 1];
        // 每个值赋值-1, -1说明是没有计算的
        Arrays.fill(cache, -1);
        // 0位和1位是已知的
        cache[0] = 0;
        cache[1] = 1;
        // 进行计算得到结果
        return fibonacci02(n, cache);
    }

    public static int fibonacci02(int n, int[] cache){
        // 计算值前,先从数组判断是否已经存在了, 存在了直接返回
        if (cache[n] != -1){
            return cache[n];
        }

        // 没有再进行计算
        int n1 = fibonacci01(n - 1);
        int n2 = fibonacci01(n - 2);

        // 计算的结果存入cache数组
        cache[n] = n1 + n2;

        // 再返回值
        return cache[n];
    }

    /**
     * 第一版
     * @param n
     * @return
     */
    public static int fibonacci01(int n){
        if (n == 0){
            return 0;
        }

        if (n == 1){
            return 1;
        }

        int n1 = fibonacci01(n - 1);
        int n2 = fibonacci01(n - 2);

        return n1 + n2;
    }
}
